
\documentclass{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{fancyhdr}

\setcounter{MaxMatrixCols}{10}
%TCIDATA{OutputFilter=LATEX.DLL}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{Created=Mon Aug 28 08:56:38 2000}
%TCIDATA{LastRevised=Thursday, December 01, 2016 09:57:43}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="General\Blank Document">}
%TCIDATA{CSTFile=LaTeX article (bright).cst}

\def \go{\char"AB ~\ignorespaces}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\setlength{\headsep}{5mm}
\setlength{\topmargin}{-15mm}
\setlength{\oddsidemargin}{-10mm}
\setlength{\textwidth}{190mm}
\setlength{\textheight}{245mm}
\newcommand{\trans}[1]{\hbox{$\hspace{0.2em}^t\hspace{-0.2em}#1$}}
\pagestyle{fancy}
\lhead{ \Large{EXERCICES MPSI}}\chead{ \large {A1. II. SOMMES, RECURRENCES, BINOME}} \rhead {\Large{R. FERRÉOL  16/17}}
\input{tcilatex}

\begin{document}


\bigskip

\fbox{II. 1) \textbf{NOTATIONS }$\dsum $\textbf{\ ET }$\dprod $}\newline

\begin{enumerate}
\item : Sommes des puissances $p$-i\`{e}mes des $n$ premiers entiers.

Posons : $a_{n}=\underset{k=1}{\overset{n}{\sum }}k=\dfrac{n(n+1)}{2}%
\;;\;b_{n}=\underset{k=1}{\overset{n}{\sum }}k^{2}\;;\;c_{n}=\underset{k=1}{%
\overset{n}{\sum }}k^{3}\;;\;d_{n}=\underset{k=1}{\overset{n}{\sum }}k^{4}.$

\begin{enumerate}
\item En remarquant que $c_{n+1}=\underset{k=0}{\overset{n}{\sum }}\left(
k+1\right) ^{3}$, montrer que $c_{n+1}=c_{n}+3b_{n}+3a_{n}+n+1$ $;$ en d\'{e}%
duire la valeur de $b_{n}$.

\item Montrer de m\^{e}me que $d_{n+1}=d_{n}+4c_{n}+6b_{n}+4a_{n}+n+1$ ; en d%
\'{e}duire la valeur de $c_{n}.$\newline
$\left[ \text{Rep}:b_{n}=\dfrac{n\left( n+1\right) \left( 2n+1\right) }{6}%
;\;c_{n}=\left( \dfrac{n(n+1)}{2}\right) ^{2}\right] $

\item * G\'{e}n\'{e}ralisation : si $S_{n}^{p}=\underset{k=0}{\overset{n}{%
\sum }}k^{p},$ montrer la formule de r\'{e}curence de Pascal (1654) : 
\begin{equation*}
\left( p+1\right) S_{n}^{p}=\left( n+1\right) ^{p+1}-\overset{p-1}{\underset{%
k=0}{\dsum }}\left( 
\begin{array}{c}
p+1 \\ 
k%
\end{array}%
\right) S_{n}^{k}.
\end{equation*}

\item * Calculer $d_{n}=S_{n}^{4}$ et v\'{e}rifier que $d_{n}=\left(
6a_{n}-1\right) b_{n}/5.$
\end{enumerate}

\item : Remplir le tableau apr\`{e}s avoir calcul\'{e} les sommes
correspondantes : 
\begin{equation*}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
$a_{i,j}=$ & $1$ & $i$ & $j$ & $i+j$ & $ij$ \\ \hline
$\underset{1\leqslant i,~j\leqslant n}{\sum }a_{i~j}=\;\;$ & $\ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ $ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  & \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  & \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \  & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \\ 
\hline
$\underset{1\leqslant i\leqslant j\leqslant n}{\sum }a_{i~j}=\;\;$ &  &  & 
&  &  \\ \hline
\end{tabular}%
\end{equation*}

\item :

\begin{enumerate}
\item Calculer $\underset{1\leqslant i,j\leqslant n}{\overset{n}{\sum }}\min
\left( i,j\right) .$

\item En d\'{e}duire la valeur de $\underset{1\leqslant i,j\leqslant n}{%
\overset{n}{\sum }}\max \left( i,j\right) ,$ puis celle de $\underset{%
1\leqslant i,j\leqslant n}{\overset{n}{\sum }}\left\vert i-j\right\vert .$
\end{enumerate}

\item * In\'{e}galit\'{e} de Tchebychev :

\begin{enumerate}
\item Montrer que 
\begin{equation*}
\sum_{1\leqslant i<j\leqslant n}\left( a_{j}-a_{i}\right) \left(
b_{j}-b_{i}\right) =n\left( \sum_{k=1}^{n}a_{k}b_{k}\right) -\left(
\sum_{k=1}^{n}a_{k}\right) \left( \sum_{k=1}^{n}b_{k}\right)
\end{equation*}

\item En d\'{e}duire que si $a_{1}\leqslant a_{2}\leqslant ...\leqslant
a_{n} $ et $b_{1}\leqslant b_{2}\leqslant ...\leqslant b_{n}$ 
\begin{equation*}
\left( \dfrac{\sum_{i=1}^{n}a_{i}}{n}\right) \left( \dfrac{%
\sum_{i=1}^{n}b_{i}}{n}\right) \leqslant \dfrac{\sum_{i=1}^{n}a_{i}b_{i}}{n}
\end{equation*}

(autrement dit, lorsque deux s\'{e}ries de $n$ nombres sont rang\'{e}s dans
l'ordre croissant, le produit de leurs moyennes est inf\'{e}rieur ou \'{e}%
gal \`{a} la moyenne de leurs produits)
\end{enumerate}

\item * :

\begin{enumerate}
\item D\'{e}montrer l'identit\'{e} de Lagrange : 
\begin{equation*}
\left( \overset{n}{\underset{k=1}{\sum }}a_{k}^{2}\right) \left( \overset{n}{%
\underset{k=1}{\sum }}b_{k}^{2}\right) =\left( \overset{n}{\underset{k=1}{%
\sum }}a_{k}b_{k}\right) ^{2}+\underset{1\leqslant i<j\leqslant n}{\sum }%
\left( a_{i}b_{j}-a_{j}b_{i}\right) ^{2}
\end{equation*}

\item En d\'{e}duire que le produit de 2 sommes de 2 carr\'{e}s (parfaits)
est encore une somme de 2 carr\'{e}s, et que plus g\'{e}n\'{e}ralement, le
produit de 2 sommes de $n$ carr\'{e}s est une somme de .... carr\'{e}s.

\item En d\'{e}duire, pour $\overrightarrow{u}=\left(
a_{1},a_{2},...,a_{n}\right) $ et $\overrightarrow{v}=\left(
b_{1},b_{2},...,b_{n}\right) \in \mathbb{R}^{n}$ \ l'in\'{e}galit\'{e} de
Cauchy-Schwarz :%
\begin{equation*}
\left\vert \overset{n}{\underset{k=1}{\sum }}a_{k}b_{k}\right\vert \leqslant 
\sqrt{\left( \overset{n}{\underset{k=1}{\sum }}a_{k}^{2}\right) }\sqrt{%
\left( \overset{n}{\underset{k=1}{\sum }}b_{k}^{2}\right) }
\end{equation*}

A quelle CNS portant sur $\overrightarrow{u}$ et $\overrightarrow{v}$ a-t-on 
\'{e}galit\'{e} entre les deux membres de cette \'{e}galit\'{e} ?
\end{enumerate}

\item * : In\'{e}galit\'{e} entre \'{e}cart-type et \'{e}cart moyen.

\begin{enumerate}
\item Montrer que si $\overset{n}{\underset{k=1}{\sum }}a_{k}=0,$ alors $%
\overset{n}{\underset{k=1}{\sum }}a_{k}^{2}\leqslant \dfrac{1}{2}\left( 
\overset{n}{\underset{k=1}{\sum }}\left\vert a_{k}\right\vert \right) ^{2}.$

Indication : partir de $\left( \overset{n}{\underset{k=1}{\sum }}%
a_{k}\right) ^{2}=0.$

\item En d\'{e}duire que si $\sigma $ est l'\'{e}cart-type de la s\'{e}rie
de nombres $\left( a_{1},a_{2},...,a_{n}\right) $ et $\sigma ^{\prime }$ son 
\'{e}cart-moyen, alors $\sigma \leqslant \sqrt{\dfrac{n}{2}}\sigma ^{\prime
}.$

Rappel : $\sigma =\sqrt{\dfrac{\overset{n}{\underset{k=1}{\sum }}\left(
a_{k}-m\right) ^{2}}{n}}$ et $\sigma ^{\prime }=\dfrac{\overset{n}{\underset{%
k=1}{\sum }}\left\vert a_{k}-m\right\vert }{n},$ o\`{u} $m$ est la moyenne
arithm\'{e}tique des a$_{k}.$
\end{enumerate}

\item * : Encadrement de Gauss de la factorielle :

\begin{enumerate}
\item Montrer que pour $n\geqslant 1,\ \ n!=\underset{_{\substack{ i+j=n+1 
\\ i\geqslant 1,j\geqslant 1}}}{\prod }\sqrt{ij}$

\item Montrer que si $i\geqslant 1$ et $j\geqslant 1,$ alors $i+j-1\leqslant
ij\leqslant \left( \dfrac{i+j}{2}\right) ^{2}.$

\item En d\'{e}duire l'encadrement : $n^{\frac{n}{2}}\leqslant n!\leqslant
\left( \dfrac{n+1}{2}\right) ^{n}.$
\end{enumerate}

\item * : Un encadrement de $\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) $:

\begin{enumerate}
\item Montrer que : 
\begin{equation*}
\dfrac{\underset{_{\substack{ 1\leqslant k\leqslant 2n  \\ k\text{ impair}}}}%
{\prod }k}{\underset{_{_{\substack{ 1\leqslant k\leqslant 2n  \\ k\text{ pair%
} }}}}{\prod }k}=\dfrac{\left( 2n\right) !}{2^{2n}\left( n!\right) ^{2}}=%
\dfrac{\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) }{4^{n}}
\end{equation*}

\item En d\'{e}duire que pour $n\geqslant 1$ : $\dfrac{4^{n}}{2n}\leqslant
\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) \leqslant \dfrac{4^{n}}{2}$.\newline
\newline
\newline
\end{enumerate}

\fbox{II 2)3) \textbf{R\'{E}CURRENCES, BIN\^{O}ME}}\newline
\newline

\item (in\'{e}galit\'{e} de Bernoulli) : Montrer que si $x\geqslant -1,$
alors pour tout $n$ entier naturel, $\left( 1+x\right) ^{n}\geqslant 1+nx.$

\begin{enumerate}
\item Par r\'{e}currence.

\item En utilisant la formule du bin\^{o}me, uniquement pour $x\geqslant 0.$

\item En utilisant la formule de Bernoulli, uniquement pour $x\geqslant 0.$

\item Proposez une quatri\`{e}me m\'{e}thode.
\end{enumerate}

\item : On donne $f(x)=\dfrac{1}{x+a}$ ; conjecturer une formule pour la d%
\'{e}riv\'{e}e $n$-i\`{e}me $f^{(n)}\left( x\right) $ et la montrer par r%
\'{e}currence.

\item : Partant de $u_{0}=1,$ calculer $u_{1},u_{2},u_{3}$ puis conjecturer
une formule pour $u_{n}$ et la d\'{e}montrer par r\'{e}currence, dans les
cas suivants :\newline

\begin{enumerate}
\item $u_{n+1}=\dfrac{u_{n}}{u_{n}+1}$

\item $u_{n+1}=\dfrac{u_{n}}{\sqrt{u_{n}^{2}+1}}$

\item $u_{n+1}=\dfrac{u_{n}}{u_{n}+2}$
\end{enumerate}

\item (nombres de Catalan) : On pose $C_{0}=1$ et $C_{n+1}=%
\sum_{k=0}^{n}C_{k}C_{n-k}.$

\begin{enumerate}
\item Calculer les 5 premiers termes de cette suite.

\item Montrer par r\'{e}currence simple que $C_{n}\geqslant 2^{n-1}$ pour
tout $n\geqslant 0.$

\item * Montrer par r\'{e}currence forte que $C_{n}\geqslant 3^{n-2}$ pour
tout $n\geqslant 0.$

\item * Tenter de montrer par une r\'{e}currence similaire \`{a} celle de c) 
$C_{n}\geqslant 4^{n-2}$ pour tout $n\geqslant 0.$ A quel endroit ceci \'{e}%
choue-t-il ? Pourquoi est-il heureux que cette d\'{e}monstration \'{e}choue ?
\end{enumerate}

\item * : Variantes de raisonnements par r\'{e}currence.

Parmi les \'{e}nonc\'{e}s suivants, lesquels permettent d'en d\'{e}duire que 
$P_{n}$ est vraie pour tout naturel $n$ ?

\begin{enumerate}
\item $P_{0}$ est vraie et pour tout naturel $n,$ $P_{n}\Rightarrow (P_{2n}$
et $P_{2n+1}).$

\item $P_{0}$ et $P_{1}$ sont vraies et pour tout naturel $n\geqslant 1,$ $%
P_{n}\Rightarrow (P_{2n}$ et $P_{2n+1}).$

\item $P_{0}$ $,P_{1},P_{2}$ sont vraies et pour tout naturel $n\geqslant 2,$
$P_{n}\Rightarrow (P_{2n}$ et $P_{2n+1}).$

\item $P_{1}$ est vraie, pour tout naturel $n\geqslant 1,$ $P_{n}\Rightarrow
P_{n-1}$ et pour tout naturel $n,$ $P_{n}\Rightarrow P_{2n}$ (r\'{e}currence
de Cauchy).

\item $P_{0}$ et $P_{1}$ sont vraies et pour tout naturel $n\geqslant 1,$ $%
P_{2n}\Rightarrow \left( P_{2n-1}~\text{et }P_{2n+1}\right) .$
\end{enumerate}

\item :

\begin{enumerate}
\item V\'{e}rifier pour tout $n\in \mathbb{N}^{\ast }$ : $\overset{n}{%
\underset{k=1}{\dsum }}k=\dfrac{n\left( n+1\right) }{2},$ et $\overset{n}{%
\underset{k=1}{\dsum }}k\left( k+1\right) =\dfrac{n\left( n+1\right) \left(
n+2\right) }{3}.$

\item Conjecturer une formule g\'{e}n\'{e}rale pour $S_{n}=\underset{k=1}{%
\overset{n}{\underset{k=1}{\overset{n}{\dsum }}k^{\overline{p}}=\dsum }}%
k\left( k+1\right) ...\left( k+p-1\right) $, o\`{u} $p$ est un naturel donn%
\'{e}, et la montrer par r\'{e}currence.

\item En d\'{e}duire les valeurs de $\overset{n}{\underset{k=1}{\dsum }}%
k^{2} $ et $\overset{n}{\underset{k=1}{\dsum }}k^{3}.$

\item \'{E}crire $\dfrac{S_{n}}{p!}$ sous la forme $\underset{k=1}{\overset{n%
}{\dsum }}\left( 
\begin{array}{c}
... \\ 
...%
\end{array}%
\right) $; en d\'{e}duire une deuxi\`{e}me fa\c{c}on de calculer $S_{n}.$

REM\ : \'{e}crite sous la forme $\underset{k=1}{\overset{n}{\dsum }}k^{%
\overline{p}}=\dfrac{n^{\overline{p+1}}}{\left( p+1\right) !},$ la formule
du $b)$ est facile \`{a} retenir !
\end{enumerate}

\item :

\begin{enumerate}
\item D\'{e}terminer un diviseur commun $>1$ aux nombres $n4^{n+1}-\left(
n+1\right) 4^{n}+1$ $\left( \text{ pour }n\geqslant 1\right) .$

\item D\'{e}terminer un diviseur commun $>1$ aux nombres $3\times
5^{2n-1}+2^{3n-2}\left( \text{ pour }n\geqslant 1\right) .$
\end{enumerate}

\item * : $n$ droites sont situ\'{e}es dans un plan, sans que deux d'entre
elles ne soient parall\`{e}les ni trois d'entre elles concourantes ; d\'{e}%
terminer le nombre de r\'{e}gions d\'{e}termin\'{e}es par ces $n$ droites.

\item * : In\'{e}galit\'{e} de convexit\'{e}.

Soit $f$ une fonction d\'{e}finie sur un intervalle $I$ et v\'{e}rifiant 
\begin{equation*}
\forall x_{1},x_{2}\in I\ \forall t\in \left[ 0,1\right] \ \ f\left( \left(
1-t\right) x_{1}+tx_{2}\right) \leqslant \left( 1-t\right) f\left(
x_{1}\right) +tf\left( x_{2}\right)
\end{equation*}

(d\'{e}finition d'une fonction convexe).

\newline
Montrer par r\'{e}currence que pour toute suite de $n$ nombres $\left(
t_{1},...,t_{n}\right) $ positifs ou nuls de somme \'{e}gale \`{a} 1 et
toute suite $\left( x_{1},...,x_{n}\right) $ de $n$ r\'{e}els appartenant 
\`{a} $I$

\begin{equation*}
f\left( \underset{i=1}{\overset{n}{\sum }}t_{i}x_{i}\right) \leqslant 
\underset{i=1}{\overset{n}{\sum }}t_{i}f\left( x_{i}\right)
\end{equation*}

\item * : In\'{e}galit\'{e} entre moyenne g\'{e}om\'{e}trique et moyenne
arithm\'{e}tique.

\begin{enumerate}
\item Montrer que si $n$ r\'{e}els positifs ont un produit \'{e}gal \`{a} 1,
alors l'un d'entre eux est $\leqslant 1$ et un autre est $\geqslant 1$ ;
montrer que ces deux nombres $x$ et $y$ v\'{e}rifient alors $x+y\geqslant
1+xy.$

\item Montrer par r\'{e}currence sur $n$ que si $x_{1},x_{2},...,x_{n}$ sont 
$n$ r\'{e}els positifs de produit \'{e}gal \`{a} 1, alors leur somme est $%
\geqslant n.$

\item En d\'{e}duire que si $x_{1},x_{2},...,x_{n}$ sont $n$ r\'{e}els
positifs, $\sqrt[n]{x_{1}x_{2}...x_{n}}\leqslant \dfrac{x_{1}+x_{2}+...+x_{n}%
}{n}.$
\end{enumerate}

\item * : In\'{e}galit\'{e} de Tchebychev g\'{e}n\'{e}ralis\'{e}e (cf ex 4).

Montrer que si $\left( a_{1},...,a_{n}\right) $ et $\left(
b_{1},...,b_{n}\right) $ sont deux suites croissantes de $n$ r\'{e}els, et $%
\left( t_{1},...,t_{n}\right) $ une suite de $n$ r\'{e}els positifs ou nuls
de somme \'{e}gale \`{a} 1, alors 
\begin{equation*}
\left( \underset{i=1}{\overset{n}{\sum }}t_{i}a_{i}\right) \left( \underset{%
i=1}{\overset{n}{\sum }}t_{i}b_{i}\right) \leqslant \underset{i=1}{\overset{n%
}{\sum }}t_{i}a_{i}b_{i}
\end{equation*}

(Commencer par le cas $n=2$ puis proc\'{e}der par r\'{e}currence ).

\item * : D\'{e}montrer qu'il existe un entier naturel $n_{0}$ \`{a} partir
duquel tout entier peut s'\'{e}crire sous la forme $5a+7b$ avec $a,b$
entiers naturels.

\item * : Dans un poly\`{e}dre convexe \`{a} $n\geqslant 4$ faces, montrer
que le nombre d'ar\^{e}tes est \'{e}gal au nombre de sommets plus $n-2$
(cette identit\'{e} s'appelle la \textit{relation d'Euler}).

\item * : Une dr\^{o}le de fa\c{c}on de d\'{e}finir la multiplication,
l'exponentiation etc...

On d\'{e}finit $f_{n}\left( a,b\right) $ pour $a,b\in \mathbb{N}^{\ast }$
par 
\begin{equation*}
\left\{ 
\begin{array}{l}
f_{1}\left( a,b\right) =a+b \\ 
f_{n}\left( a,1\right) =a\text{ pour tout entier }n\geqslant 2,\text{ }%
a\geqslant 1 \\ 
f_{n}\left( a,b\right) =f_{n-1}\left( a,\;f_{n}\left( a,b-1\right) \right) 
\text{ pour tout entier }a\geqslant 1,b\geqslant 2,n\geqslant 2%
\end{array}%
\right.
\end{equation*}%
Calculer $\;f_{2}\left( a,b\right) ,\;f_{3}\left( a,b\right) ,\;f_{4}\left(
a,b\right) ,f_{5}\left( a,2\right) ,\;f_{n}\left( 2,2\right) ,\;f_{5}\left(
3,3\right) $.\newline

\item : Calculer $3^{5}$ en base $2$ en utilisant la formule du bin\^{o}me.

\item : Montrer que pour $n$ entier $\geqslant 1,$ $\left( n+1\right)
^{n}\geqslant 2n^{n}.$

\item : Somme altern\'{e}e partielle d'une ligne du triangle de Pascal.

Montrer la relation : $\underset{k=0}{\overset{p}{\dsum }}\left( -1\right)
^{k}\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) =\left( -1\right) ^{p}\left( 
\begin{array}{c}
n-1 \\ 
p%
\end{array}%
\right) $ (pour $0\leqslant p\leqslant n-1)$

\begin{enumerate}
\item En partant de $\left( 
\begin{array}{c}
n-1 \\ 
p%
\end{array}%
\right) =\left( 
\begin{array}{c}
n \\ 
p%
\end{array}%
\right) -\left( 
\begin{array}{c}
n-1 \\ 
p-1%
\end{array}%
\right) $ et en it\'{e}rant.

\item Par r\'{e}currence sur $n.$

\item Par r\'{e}currence sur $p,$ avec la convention que si $p\geqslant
n,\left( 
\begin{array}{c}
n-1 \\ 
p%
\end{array}%
\right) =0.$
\end{enumerate}

\item :

\begin{enumerate}
\item Calculer $\overset{n}{\underset{k=1}{\dsum }}k\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) $ en transformant l'expression $k\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) $ de sorte que le nombre situ\'{e} avant le coefficient binomial ne d%
\'{e}pende pas de $k.$

\item Calculer $\underset{k=p}{\overset{n}{\dsum }}k\left( 
\begin{array}{c}
k-1 \\ 
p-1%
\end{array}%
\right) ,$ pour $n\geqslant p.$
\end{enumerate}

\item : Calculer \`{a} l'aide de la fonction $f$ d\'{e}finie par $f\left(
x\right) =\left( 1+x\right) ^{n}$:

\begin{enumerate}
\item $\overset{n}{\underset{k=1}{\dsum }}k\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) $

\item $\overset{n}{\underset{k=1}{\dsum }}\left( -1\right) ^{k}k\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) $

\item $\overset{n}{\underset{k=2}{\dsum }}k\left( k-1\right) \left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) $

\item $\overset{n}{\underset{k=0}{\dsum }}\dfrac{\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) }{k+1}.$
\end{enumerate}

\item * :

\begin{enumerate}
\item Calculer le coefficient de $x^{k}$ dans $\left( 1+x\right) ^{p+q}$
puis dans $\left( 1+x\right) ^{p}\left( 1+x\right) ^{q}$ ; en d\'{e}duire la 
\textit{formule de convolution, }ou\textit{\ de Van der Monde} : $\underset{%
i+j=k}{\dsum }\left( 
\begin{array}{c}
p \\ 
i%
\end{array}%
\right) \left( 
\begin{array}{c}
q \\ 
j%
\end{array}%
\right) =\left( 
\begin{array}{c}
p+q \\ 
k%
\end{array}%
\right) $ ; la v\'{e}rifier pour $k=2,p=3,q=4$.

\item Que retrouve-t-on pour $p=q=k=n$ ?

\item Montrer que plus g\'{e}n\'{e}ralement, le produit scalaire de la ligne 
$p$ par la ligne $q$ du triangle de Pascal est \'{e}gal \`{a} $\left( 
\begin{array}{c}
p+q \\ 
p%
\end{array}%
\right) .$

\item D\'{e}duire de la formule de convolution la formule : $\underset{i+j=k}%
{\dsum }i\left( 
\begin{array}{c}
p \\ 
i%
\end{array}%
\right) \left( 
\begin{array}{c}
q \\ 
j%
\end{array}%
\right) =p\left( 
\begin{array}{c}
p+q-1 \\ 
k-1%
\end{array}%
\right) $ (utiliser

$i\left( 
\begin{array}{c}
p \\ 
i%
\end{array}%
\right) =p\left( 
\begin{array}{c}
p-1 \\ 
i-1%
\end{array}%
\right) )$ $;$ en d\'{e}duire que $\overset{n}{\underset{k=0}{\dsum }}%
k\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) ^{2}=\dfrac{n}{2}\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) .$
\end{enumerate}

\item *: Calculer $\underset{0\leqslant i\leqslant j\leqslant n}{\dsum }%
\left( 
\begin{array}{c}
j \\ 
i%
\end{array}%
\right) \left( 
\begin{array}{c}
n-j \\ 
j-i%
\end{array}%
\right) $ en utilisant la formule de convolution, exercice pr\'{e}c\'{e}dent.

\item * : Formule de convolution, preuve par r\'{e}currence. On admet dans
cet exercice que si l'on pose $\left( 
\begin{array}{c}
b \\ 
a%
\end{array}%
\right) =0$ pour tous entiers $a,b$ ne v\'{e}rifiant pas $0\leq a\leq b,$ la
relation de Pascal $\left( 
\begin{array}{c}
b+1 \\ 
a%
\end{array}%
\right) =\left( 
\begin{array}{c}
b \\ 
a%
\end{array}%
\right) +\left( 
\begin{array}{c}
b \\ 
a-1%
\end{array}%
\right) $ est  valable pour tous les entiers $a,b.$

\begin{enumerate}
\item On demande de d\'{e}montrer par r\'{e}currence sur $n$ que pour tous
entiers naturels $m,p$ :%
\begin{equation*}
\left( 
\begin{array}{c}
m \\ 
p%
\end{array}%
\right) =\underset{k=0}{\overset{n}{\dsum }}\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) \left( 
\begin{array}{c}
m-n \\ 
p-k%
\end{array}%
\right) 
\end{equation*}

\item Retrouver la formule $\underset{k=0}{\overset{n}{\dsum }}\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) ^{2}=\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) .$

\item V\'{e}rifier que la formule du a. est bien \'{e}quivalente \`{a} la
formule de convolution (exercice 28).
\end{enumerate}

\item * : Trouver une formule issue de l'\'{e}galit\'{e} triviale : $\left(
1+2x\right) ^{n}=\left( 1+x+x\right) ^{n}.$

\item * : Que vaut $\overset{n}{\underset{k=0}{\dsum }}\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) \left( x-1\right) ^{k}$ ? Que peut on en d\'{e}duire ?

\item : Donner la valeur du coefficient de $x^{2n}$ dans $\left(
x^{2}-1\right) ^{2n}$, puis dans $\left( x-1\right) ^{2n}\left( x+1\right)
^{2n}$. En d\'{e}duire la valeur de $\underset{k=0}{\overset{2n}{\sum }}%
\left( -1\right) ^{k}\left( 
\begin{array}{c}
2n \\ 
k%
\end{array}%
\right) ^{2}$.

\item * : On pose $S_{n}=\overset{n}{\underset{k=0}{\dsum }}2^{k}\left( 
\begin{array}{c}
2n-k \\ 
n%
\end{array}%
\right) $ ; en utilisant la relation de Pascal, montrer que $S_{n+1}=2\left(
S_{n}+\dfrac{1}{2}\left( 
\begin{array}{c}
2n+1 \\ 
n%
\end{array}%
\right) \right) +\dfrac{1}{2}\left( S_{n+1}-\left( 
\begin{array}{c}
2n+2 \\ 
n+1%
\end{array}%
\right) \right) $; simplifier cette relation entre $S_{n+1}$ et $S_{n}$ et
en d\'{e}duire la valeur de $S_{n}.$\newline

\item * : Puissances factorielles descendantes et formule de Van der Monde :

\begin{enumerate}
\item \'{E}tant donn\'{e} un r\'{e}el $x$ et un entier $n\geqslant 1,$ on
note $x^{\underline{n}}$ et on lit "$x$ puissance $n$ descendant" le nombre $%
x\left( x-1\right) ..\left( x-n+1\right) $ , avec pour convention $x^{%
\underline{0}}=1$ ; montrer que 
\begin{equation*}
\left( x+y\right) ^{\underline{n}}=\sum_{k=0}^{n}\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) x^{\underline{n-k}}\ y^{\underline{k}}
\end{equation*}

\item D\'{e}finir de m\^{e}me les puissances factorielles montantes. A t-on
la m\^{e}me pseudo-formule du bin\^{o}me ?
\end{enumerate}

\item * : D\'{e}montrer que pour $n\geqslant 1$, $\dfrac{4^{n}}{2\sqrt{n}}%
\leqslant \left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) \leqslant \dfrac{4^{n}}{\sqrt{2n}}\,.$\newline
[En fait, la meilleure majoration est : $\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) \leqslant \dfrac{4^{n}}{\sqrt{\pi n}}$, mais cela n\'{e}cessite des
techniques d'analyse]$.$

\item * : D\'{e}montrer par r\'{e}currence sur $k,$ que pour $1\leqslant
k\leqslant n,\left( 
\begin{array}{c}
n \\ 
k%
\end{array}%
\right) \leqslant \left( \dfrac{en}{k}\right) ^{k}.$

\item * : Pour $n,p\in \mathbb{N},$ on pose $u_{n,p}=\dfrac{\left( 2n\right)
!\left( 2p\right) !}{n!p!\left( n+p\right) !}.$

\begin{enumerate}
\item Calculer $u_{n+1,p}+u_{n,p+1}$ et en d\'{e}duire que $u_{n,p}$ est
entier pour tout $n$ et pour tout $p.$

\item En d\'{e}duire que $\left( 
\begin{array}{c}
n+p \\ 
n%
\end{array}%
\right) $ divise $\left( 
\begin{array}{c}
2n \\ 
n%
\end{array}%
\right) \times \left( 
\begin{array}{c}
2p \\ 
p%
\end{array}%
\right) .$
\end{enumerate}

\item * : Soit $P\left( n,p\right) $ un \'{e}nonc\'{e} d\'{e}pendant de deux
variables enti\`{e}res naturelles.

\begin{enumerate}
\item Je sais que, pour tout $\left( n,p\right) \in \mathbb{N}^{2},$ si $%
P\left( n,p\right) $ est vrai alors $P\left( n+1,p\right) $ est vrai aussi.
Quelles propri\'{e}t\'{e}s suppl\'{e}mentaires me suffit--il d'avoir pour 
\^{e}tre s\^{u}r que $P\left( n,p\right) $ est vrai pour tout $\left(
n,p\right) \in \mathbb{N}^{2}$ ?

\item M\^{e}me question, lorsque je sais que si pour $n,p\geqslant 1$\ $%
\;P\left( n-1,p\right) $ et $P\left( n,p-1\right) $ sont vrais simultan\'{e}%
ment, alors $P\left( n,p\right) $ est vrai.

\item Je sais que $K_{n}^{0}=K_{0}^{p}=1$ pour tout $n$ et $p$ dans $\mathbb{%
N}.$ \newline
Je sais aussi que $K_{n}^{p}=K_{n-1}^{p}+K_{n}^{p-1}$ pour tout $n$ et $p$
dans $\mathbb{N}.$ \newline
Que vaut $K_{n}^{p}$ ?
\end{enumerate}

\item * : \'{E}tudier le triangle infini 
\begin{equation*}
\begin{tabular}{lllllllll}
&  &  &  & $1$ &  &  &  &  \\ 
&  &  & $\dfrac{1}{2}$ &  & $\dfrac{1}{2}$ &  &  &  \\ 
&  & $\dfrac{1}{3}$ &  & $\dfrac{1}{6}$ &  & $\dfrac{1}{3}$ &  &  \\ 
& $\dfrac{1}{4}$ &  & $\dfrac{1}{12}$ &  & $\dfrac{1}{12}$ &  & $\dfrac{1}{4}
$ &  \\ 
$\dfrac{1}{5}$ &  & $\dfrac{1}{20}$ &  & $\dfrac{1}{30}$ &  & $\dfrac{1}{20}$
&  & $\dfrac{1}{5}$%
\end{tabular}%
\end{equation*}

\fbox{II. 4) \textbf{FORMULE DE BERNOULLI}}\newline
\begin{equation*}
a^{n}-b^{n}=\left( a-b\right) \overset{n-1}{\underset{k=0}{\dsum }}%
a^{n-1-k}b^{k}\;;\;a^{n}+b^{n}=\left( a+b\right) \overset{n-1}{\underset{k=0}%
{\dsum }}\left( -1\right) ^{k}a^{n-1-k}b^{k}\text{ pour }n\text{ impair}
\end{equation*}

\item :

\begin{enumerate}
\item Montrer que pour $0<x<y$ r\'{e}els, on a : 
\begin{equation*}
\dfrac{1}{3\sqrt[3]{y^{2}}}<\dfrac{\sqrt[3]{y}-\sqrt[3]{x}}{y-x}<\dfrac{1}{3%
\sqrt[3]{x^{2}}}
\end{equation*}

\item Interpr\'{e}ter graphiquement ces in\'{e}galit\'{e}s (consid\'{e}rer
la courbe de la fonction $x\longmapsto \sqrt[3]{x})$

\item G\'{e}n\'{e}raliser.
\end{enumerate}

\item $n$ est un entier $\geqslant 1.$

\begin{enumerate}
\item Montrer que si $a\geqslant b\geqslant 0$ alors $a^{n}-b^{n}\geqslant
nb^{n-1}\left( a-b\right) .$

\item * : En d\'{e}duire que si $(x,y,z)\in \left( \mathbb{N}^{\ast }\right)
^{3}$ est solution de l'\'{e}quation de Fermat $x^{n}+y^{n}=z^{n},$ alors $x$
et $y$ sont $\geqslant n$ (en r\'{e}alit\'{e}, cette \'{e}quation n'a jamais
de solution dans $\left( \mathbb{N}^{\ast }\right) ^{3}$ pour $n\geqslant 3,$
mais la d\'{e}monstration en est beaucoup, beaucoup plus difficile...).
\end{enumerate}

\item :

\begin{enumerate}
\item Montrer que la diff\'{e}rence de deux puissances de 10 est toujours
divisible par 9.

\item En d\'{e}duire que si l'on effectue une permutation sur les chiffres
d'un nombre (par exemple, on \'{e}crit 1327 \`{a} la place de 7312),
l'erreur que l'on commet est toujours divisible par 9.
\end{enumerate}

\item Montrer que si $n$ n'est pas premier, le nombre qui s'\'{e}crit $%
\underset{n\times 1}{\underbrace{1...1}}$ en base $a$ ($a$ entier $\geqslant
2$) n'est pas premier.

\item : Montrer que si $n$ n'est pas une puissance de 2, le nombre qui s'%
\'{e}crit 1$\underset{\left( n-1\right) \times 0}{\underbrace{00...00}1}$ en
base $a$ ($a$ entier $\geqslant 2$) n'est pas premier.
\end{enumerate}

\end{document}
